package pro.softzhang.algo.lc0;

import pro.softzhang.algo.flag.difficulty.DRed;

import java.util.Stack;

@DRed
public class LC84_LargestRectangleInHistogram {
    public static void main(String[] args) {
        int[] heights = {2,1,5,6,2,3};
        int largest = new Solution1().largestRectangleArea(heights);
        System.out.println(largest);
    }

    /**
     * 暴力法
     * 时间复杂度太高，通不过。
     */
    static class Solution {
        public int largestRectangleArea(int[] heights) {
            int largestArea = 0;
            for (int i = 0; i < heights.length; i++) {
                int minHeight = heights[i];
                for (int j = i; j < heights.length; j++) {
                    minHeight = Math.min(minHeight, heights[j]);
                    largestArea = Math.max(largestArea,  minHeight * (j - i + 1));
                }
            }
            return largestArea;
        }
    }

    static class Solution1 {
        public int largestRectangleArea(int[] heights) {
            Stack<Integer> stack = new Stack<>();
            stack.push(-1);
            int largestArea = 0;
            for (int i = 0; i < heights.length; i++) {
                while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                    int height = heights[stack.pop()];
                    int width = i - stack.peek() - 1;
                    largestArea = Math.max(largestArea, height * width);
                }
                stack.push(i);
            }
            while (stack.peek() != -1) {
                int height = heights[stack.pop()], width = heights.length - stack.peek() - 1;
                largestArea = Math.max(largestArea, height * width);
            }
            return largestArea;
        }
    }
}



